/*
 *  Copyright (C) 2010 Martin Haulrich <mwh.isv@cbs.dk> and Matthias Buch-Kromann <mbk.isv@cbs.dk>
 *
 *  This file is part of the IncrementalParser package.
 *
 *  The IncrementalParser program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU Lesser General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
package org.osdtsystem.incparser.learners;

import org.osdtsystem.incparser.features.FeatureVector;
import org.osdtsystem.incparser.features.WeightVectorDense;
import org.osdtsystem.incparser.features.WeightVector;
import java.util.List;

/**
 * 'upd' argument in update method should be:
 *    number of iteration * number of instances - (number of instances * (current iteration - 1) + (current instance + 1) + 1)
 *
 * @author Martin Haulrich and Matthias Buch-Kromann
 */
public class MIRALearner extends AbstractLearnerK {
    WeightVector weights;
    WeightVector sumWeights;
    int updates;
    final boolean average;

    public MIRALearner(int paramSize) {
        this(paramSize, true);
    }

    public MIRALearner(int paramSize, boolean average) {
        this.average = average;
        weights = new WeightVectorDense(paramSize);
        sumWeights = new WeightVectorDense(paramSize);
        updates = 0;
    }

    @Override
    public WeightVector weights() {
        return weights;
    }

    @Override
    public void averageWeights() {
        weights.clear();
        sumWeights.addTo(1f / updates, weights);
    }

    @Override
    public void updateK(FeatureVector goldVector, List<FeatureVector> systemVectors, 
            List<Double> loss, double upd) {
        updates++;

        int K = systemVectors.size();

        FeatureVector[] distVectors = new FeatureVector[K];
        double[] tLoss = new double[K];

        double goldScore = weights.innerProduct(goldVector);

        for (int k = 0; k < K; k++) {

            double score = weights.innerProduct(systemVectors.get(k));
            double scoreDiff = goldScore - score;

            tLoss[k] = loss.get(k) - scoreDiff;

            distVectors[k] = goldVector.subtract(systemVectors.get(k));
        }

        double[] alpha = hildreth(distVectors, tLoss);

        for (int k = 0; k < K; k++) {
            updateWeights(upd, alpha[k], distVectors[k]);
        }

    }

    private void updateWeights(double upd, double alpha, FeatureVector fv) {
        float alphaAsFloat = (float) alpha;
        float updAlpha = (float) (alpha * upd);
        fv.addTo(alphaAsFloat, weights);
        fv.addTo(updAlpha, sumWeights);
    }

    /**
     *  * This method is almost a exact copy of the chuLiuEdmonds algortihm from the MSTParser-project
     *   http://sourceforge.net/projects/mstparser/
     */
    private double[] hildreth(FeatureVector[] a, double[] b) {

        int i;
        int max_iter = 10000;
        double eps = 0.00000001;
        double zero = 0.000000000001;

        double[] alpha = new double[b.length];

        double[] F = new double[b.length];
        double[] kkt = new double[b.length];
        double max_kkt = Double.NEGATIVE_INFINITY;

        int K = a.length;

        double[][] A = new double[K][K];
        boolean[] is_computed = new boolean[K];
        for (i = 0; i < K; i++) {
//            A[i][i] = a[i].dotProduct(a[i]);
            A[i][i] = a[i].innerProduct(a[i]);
            is_computed[i] = false;
        }

        int max_kkt_i = -1;

        for (i = 0; i < F.length; i++) {
            F[i] = b[i];
            kkt[i] = F[i];
            if (kkt[i] > max_kkt) {
                max_kkt = kkt[i];
                max_kkt_i = i;
            }
        }

        int iter = 0;
        double diff_alpha;
        double try_alpha;
        double add_alpha;

        while (max_kkt >= eps && iter < max_iter) {

            diff_alpha = A[max_kkt_i][max_kkt_i] <= zero ? 0.0 : F[max_kkt_i] / A[max_kkt_i][max_kkt_i];
            try_alpha = alpha[max_kkt_i] + diff_alpha;
            add_alpha = 0.0;

            if (try_alpha < 0.0) {
                add_alpha = -1.0 * alpha[max_kkt_i];
            } else {
                add_alpha = diff_alpha;
            }

            alpha[max_kkt_i] = alpha[max_kkt_i] + add_alpha;

            if (!is_computed[max_kkt_i]) {
                for (i = 0; i < K; i++) {
//                    A[i][max_kkt_i] = a[i].dotProduct(a[max_kkt_i]); // for version 1
                    A[i][max_kkt_i] = a[i].innerProduct(a[max_kkt_i]);
                    is_computed[max_kkt_i] = true;
                }
            }

            for (i = 0; i < F.length; i++) {
                F[i] -= add_alpha * A[i][max_kkt_i];
                kkt[i] = F[i];
                if (alpha[i] > zero) {
                    kkt[i] = Math.abs(F[i]);
                }
            }

            max_kkt = Double.NEGATIVE_INFINITY;
            max_kkt_i = -1;
            for (i = 0; i < F.length; i++) {
                if (kkt[i] > max_kkt) {
                    max_kkt = kkt[i];
                    max_kkt_i = i;
                }
            }
            iter++;
        }
        return alpha;
    }
}
